package str;

import java.util.HashMap;
import java.util.Map;

/**
 * leet-code(20) 有效的括号
 *
 * @author Ringo
 * @date 2022/1/5 22:24
 */
public class ValidParentheses {

    public static void main(String[] args) {
        String s1 = "()";
        String s2 = "()[]{}";
        String s3 = "(]";
        System.out.println(isValid(s1));
        System.out.println(isValid(s2));
        System.out.println(isValid(s3));

    }


    public static boolean isValid(String s) {
        if (s == null || s.length() < 2)
            return false;
        // 开始栈是空的
        int top = -1;
        char[] stack = new char[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(')
                stack[++top] = ')';
            else if (s.charAt(i) == '[')
                stack[++top] = ']';
            else if (s.charAt(i) == '{')
                stack[++top] = '}';
            else {
                // 栈空了 就直接错误了
                if (top < 0)
                    return false;
                // 出栈和当前的值做对比
                if (stack[top--] != s.charAt(i))
                    return false;
            }
        }
        return top == -1;
    }

    public static boolean isValid2(String s) {
        if (s == null) return true;
        if (s.length() % 2 != 0) return false;

        Map<Character, Character> map = new HashMap<Character, Character>() {
            {
                put(')', '(');
                put(']', '[');
                put('}', '{');
            }
        };

        char[] stack = new char[s.length()];
        int p = -1;

        for (int i = 0; i < s.length(); ++i) {
            if (map.containsValue(s.charAt(i))) {
                stack[++p] = s.charAt(i);
            } else {
                if (p == -1 || map.get(s.charAt(i)) != stack[p--]) return false;
            }
        }
        return p == -1;
    }
}
